/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package minimalshift;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import org.jgrapht.DirectedGraph;
import org.jgrapht.alg.EdmondsKarpMaximumFlow;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;

/**
 *
 * @author Michal
 */
public class MinCostMaxFlow {

	DefaultDirectedWeightedGraph<Integer, GraphEdge> normal;
	Set<Integer> opts = new HashSet<>();

	public MinCostMaxFlow(
			DefaultDirectedWeightedGraph<Integer, GraphEdge> g) {
		normal = g;
	}

	public Map<GraphEdge, Double> getResult(int source, int sink) {
		Map<GraphEdge, Double> result = maxFlow(normal, source, sink);
		//return result;
		int cost = GraphManager.getCost(result);
		//System.out.println("Zacatecni cena "+cost);
		Map<GraphEdge, Double> optimized = cancelCycle(result);

		while (optimized != null) {
			cost = GraphManager.getCost(optimized);
			//System.out.println("Optimalizovat na "+cost);
			result = optimized;
			optimized = cancelCycle(result);
		}

		return result;
	}

	private Map<GraphEdge, Double> cancelCycle(Map<GraphEdge, Double> res) {
		DefaultDirectedWeightedGraph<Integer, GraphEdge> graph = GraphManager.getClone(normal);

		Map<GraphEdge, GraphEdge> EdgeMapper = new HashMap<>();
		int counter = 0;
		for (Map.Entry<GraphEdge, Double> e : res.entrySet()) {
			if (e.getValue() > 0) {
				counter++;
				GraphEdge edge = e.getKey();
				int newSource = normal.getEdgeTarget(edge);
				int newTarget = normal.getEdgeSource(edge);
				int newCost = edge.getCost() * -1;
				GraphEdge backEdge = new GraphEdge(false, newCost);
				EdgeMapper.put(backEdge, edge);
				graph.addEdge(newSource, newTarget, backEdge);
				graph.setEdgeWeight(backEdge, e.getValue());
				double weight = normal.getEdgeWeight(edge) - e.getValue();
				if (weight == 0) {
					graph.removeEdge(edge);
				} else {
					graph.removeEdge(edge);
					GraphEdge forwEdge = new GraphEdge(false,edge.getCost());
					EdgeMapper.put(forwEdge, edge);
					graph.addEdge(newTarget,newSource,forwEdge);
					graph.setEdgeWeight(forwEdge, weight);
				}
			}
		}

		Map<GraphEdge, Double> newSolution = null;
		for (int i : graph.vertexSet()) {
			NegativeCostCycleDetector detector = new NegativeCostCycleDetector(graph, i);

			if (!detector.hasNegativeCycle()) {
				continue;
			}

			List<GraphEdge> edges = detector.getNegativeCycleVertices();

			double minFlow = Double.MAX_VALUE;
			for (GraphEdge e : edges) {
				double newMin = graph.getEdgeWeight(e);
				if (newMin < minFlow) {
					minFlow = newMin;
				}
			}
			if (minFlow == 0) {
				continue;
			}
			if (minFlow < 0) {
				continue;
			}
			
			newSolution = new HashMap(res);
			for (GraphEdge e : edges) {
				if (e.getCost() > 0) {
					GraphEdge edge = EdgeMapper.get(e);
					if(edge==null){
						edge = e;
					}
					double newFlow = res.get(edge) + minFlow;
					newSolution.put(edge, newFlow);
				}
				if (e.getCost() < 0) {
					GraphEdge edge = EdgeMapper.get(e);
					double newFlow = res.get(edge) - minFlow;
					newSolution.put(edge, newFlow);
				}
			}
			break;
		}
		return newSolution;
	}

	private Map<GraphEdge, Double> maxFlow(DirectedGraph g, int source, int sink) {
		EdmondsKarpMaximumFlow<Integer, GraphEdge> edmont =
				new EdmondsKarpMaximumFlow<>(g);
		edmont.calculateMaximumFlow(source, sink);
		return edmont.getMaximumFlow();
	}
}
